2382. Графическая маска

В одном из режимов программного пакета Grafix пользователь выделяет часть полотна, используя непрозрачные прямоугольники. Графическое изображение, которое используется в качестве полотна, имеет 400 точек в высоту и 600 точек в ширину. Как только прямоугольники окажутся выделенными, пользователь может выполнить графические операции в невыделенных областях полотна, известных как дырки. Дыркой называется максимальный набор соседних пикселей, не принадлежащих ни одному из непрозрачных прямоугольников. Два пикселя являются соседними, если они прилегают друг к другу по горизонтали или вертикали. Отношение соседства является транзитивным.

На полотне выделено несколько прямоугольников. Найти размеры всех дырок (в точках) и вывести их в возрастающем порядке.

Левый рисунок содержит две дырки, а правый девять.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество прямоугольников n (1 ≤ n ≤ 50). Каждая из следующих n строк описывает координаты противоположных углов прямоугольника в формате "строка столбец строка столбец" (0 ≤ строка ≤ 399, 0 ≤ столбец ≤ 599). Первая пара чисел задает координаты верхнего левого угла, а вторая пара – координаты нижнего правого.

Выход. Для каждого теста вывести в отдельной строке размеры всех дырок в возрастающем порядке. Если для некоторого теста дырки на полотне будут отсутствовать, то вывести пустую строку.

Пример входа	Пример выхода
1 0 292 399 307 4 48 192 351 207 48 392 351 407 120 52 135 547 260 52 275 547	116800 116800 22816 192608

РЕШЕНИЕ

графы – поиск в глубину

Анализ алгоритма

Будем трактовать точки полотна, покрытые хотя бы одним прямоугольником, водой, а точки, не покрытые ни одним прямоугольником, сушей. Тогда дырками будут являться острова. Задача сводится к нахождению количества островов и вычислению их размеров, что решается при помощи поиска в глубину.

При запуске процедуры поиска в глубину используется стек. Размеры слоя достаточно большие, поэтому потребуется большое количество памяти. В связи с архитектурой компьютерных программ, память, доступная для рекурсивных вызовов, мала. Поэтому следует брать память из кучи, что можно реализовать, например, используя структуру данных stack. Однако если стек промоделировать при помощи глобального массива, то скорость работы увеличится в разы.

Реализация алгоритма

Входной слой будем хранить в целочисленном массиве m. Объявим массив точек _Stack, в котором будем моделировать работу стека.

int m[400][600];

struct Point

{

int x, y;

Point(int x = 0, int y = 0) {this->x = x; this->y = y;}

} _Stack[1000000];

Нерекурсивная реализация поиска в глубину из точки (i, j). Функция dfs возвращает размер дырки, которой принадлежит точка (i, j).

int dfs(int i,int j)

{

int res = 0;

_Stack[ptr++] = Point(i,j);

Point node;

while(ptr > 0)

{

node = _Stack[--ptr];

if (m[node.x][node.y]) continue;

m[node.x][node.y] = 1; res++;

if ((node.x < 399) && !m[node.x+1][node.y])

_Stack[ptr++] = Point(node.x+1,node.y);

if ((node.x > 0) && !m[node.x-1][node.y])

_Stack[ptr++] = Point(node.x-1,node.y);

if ((node.y < 599) && !m[node.x][node.y+1])

_Stack[ptr++] = Point(node.x,node.y+1);

if ((node.y > 0) && !m[node.x][node.y-1])

_Stack[ptr++] = Point(node.x,node.y-1);

}

return res;

}

Просматриваем слой слева направо и сверху вниз. Для каждой точки (j, k), не покрытой никаким прямоугольником (m[j][k] = 0), запускаем поиск в глубину dfs(j,k). Размеры дырок сохраняем в массиве res. По окончании работы функции sortedAreas сортируем массив дырок res и возвращаем его.

vector<int> sortedAreas(void)

{

vector<int> res;

int j, k;

for(ptr = j = 0; j < 400; j++)

for(k = 0; k < 600; k++)

if (!m[j][k]) res.push_back(dfs(j,k));

sort(res.begin(),res.end());

return res;

}

Основная часть программы. Считываем прямоугольники и наносим их на маскирующий слой. Таким образом, если точка (j, k) остается не покрытой никаким прямоугольником, то m[j][k] = 0. Иначе m[j][k] устанавливается равным 1.

while(scanf("%d",&n) == 1)

{

memset(m,0,sizeof(m));

for(i = 0; i < n; i++)

{

scanf("%d %d %d %d",&Top, &Left, &Down, &Right);

for(j = Top; j <= Down; j++)

for(k = Left; k <= Right; k++) m[j][k] = 1;

}

При помощи нерекурсивного поиска в глубину вычисляем размеры всех дырок и выводим их в возрастающем порядке.

res = sortedAreas();

for(i = 0; i < res.size(); i++) printf("%d ",res[i]);

printf("\n");

}